package com.practice.zuocy.base.class12;

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;

/**
 * 【题目】
 * 【leetcode 691. 贴纸拼词】（TODO：从左到右不断尝试）
 * 给定一个字符串str，给定一个字符串类型的数组arr。
 * arr里的每一个字符串，代表一张贴纸，你可以把单个字符剪开使用，目的是拼出str来。(TODO:每种贴纸可以使用任意张)
 * 返回需要至少多少章贴纸可以完成这个任务。
 * 【例子】:
 * str="babac", arr={"ba", "c", "abcd"}
 * 至少需要两张贴纸“ba”和"abcd"，因为使用这两张贴纸，把每一个字符单独剪剪开，
 * 含有2个'a'、2个'b'、1个'c'。是可以拼出str的。所以返回2。
 */
public class Code02_StickersToSpellWord {

    // 暴力递归主函数
    public static int myMain(String aim, String[] arr){
        if (aim==null||aim.length()==0){
            return 0;
        }
        if (arr==null || arr.length==0){
            return -1;
        }
        // TODO: 判断aim中的字符种类个数是否 < arr中的字符种类个数
        HashSet<Character> haveCharacters = new HashSet<>();
        for (int i = 0; i < arr.length; i++) {
            String curString = arr[i];
            char[] chars = curString.toCharArray();
            for (int j = 0; j < chars.length; j++) {
                haveCharacters.add(chars[j]);
            }
        }
        char[] aimChars = aim.toCharArray();
        for (int i = 0; i < aimChars.length; i++) {
            if (!haveCharacters.contains(aimChars[i])){
                return -1;
            }
        }
        return myProcess(aim, arr);
    }

    // 暴力递归
    // 还剩下rest中的字符没有搞定，请继续在arr中选择第一张使用的贴纸，返回最少使用的贴纸数量
    public static int myProcess(String rest, String[] arr) {

        if (rest.equals("")) {
            return 0;
        }

        int next = Integer.MAX_VALUE;
        // 搞定rest的第一张贴纸是啥
        for (String first : arr) {
            char[] firstChars = first.toCharArray();
            HashMap<Character, Integer> firstMap = new HashMap<>();
            for (int i = 0; i < firstChars.length; i++) {
                if (firstMap.containsKey(firstChars[i])) {
                    firstMap.put(firstChars[i], firstMap.get(firstChars[i]) + 1);
                } else {
                    firstMap.put(firstChars[i], 1);
                }
            }
            char[] oldRestChars = rest.toCharArray();
            HashMap<Character, Integer> oldRestMap = new HashMap<>();
            for (int i = 0; i < oldRestChars.length; i++) {
                if (oldRestMap.containsKey(oldRestChars[i])) {
                    oldRestMap.put(oldRestChars[i], oldRestMap.get(oldRestChars[i]) + 1);
                } else {
                    oldRestMap.put(oldRestChars[i], 1);
                }
            }
            // TODO：如果first中一个字符也不在rest中，直接跳过这张贴纸
            int containNumber = 0;

            // old-first
            HashMap<Character, Integer> newRestMap = new HashMap<>();
            Set<Character> oldCharacters = oldRestMap.keySet();
            for (Character ch : oldCharacters) {
                if (firstMap.containsKey(ch) && (firstMap.get(ch) < oldRestMap.get(ch))) {
                    containNumber++;
                    newRestMap.put(ch, oldRestMap.get(ch) - firstMap.get(ch));
                } else if (firstMap.containsKey(ch) && (firstMap.get(ch) >= oldRestMap.get(ch))) {
                    containNumber++;
                    continue;
                } else {
                    newRestMap.put(ch, oldRestMap.get(ch));
                }
            }
            if (containNumber==0){
                continue;
            }
            String newRest = "";
            Set<Character> newRestCharacters = newRestMap.keySet();
            for (Character newCh : newRestCharacters) {
                int count = newRestMap.get(newCh);
                for (int i = 1; i <= count; i++) {
                    newRest += newCh;
                }
            }

            int cur = myProcess(newRest, arr);
            // 当前使用了1张贴纸所以cur+1
            next = Math.min(next, cur+1);
        }

        return next;
    }


    // 傻缓存主函数
    public static int myCacheMain(String aim, String[] arr){
        if (aim==null||aim.length()==0){
            return 0;
        }
        if (arr==null || arr.length==0){
            return -1;
        }
        HashMap<String, Integer> dp = new HashMap<>();

        // TODO（强调）: 判断aim中的字符种类个数是否 <= arr中的字符种类个数，
        //  如果aim中存在arr中不包含的字符直接返回-1
        HashSet<Character> haveCharacters = new HashSet<>();
        for (int i = 0; i < arr.length; i++) {
            String curString = arr[i];
            char[] chars = curString.toCharArray();
            for (int j = 0; j < chars.length; j++) {
                haveCharacters.add(chars[j]);
            }
        }
        char[] aimChars = aim.toCharArray();
        for (int i = 0; i < aimChars.length; i++) {
            if (!haveCharacters.contains(aimChars[i])){
                return -1;
            }
        }
        return myCacheProcess(aim, arr, dp);
    }



    // 暴力递归超时，改用傻缓存
    public static int myCacheProcess(String rest, String[] arr, HashMap<String, Integer> dp) {

        if (dp.containsKey(rest)){
            return dp.get(rest);
        }

        if (rest.equals("")) {
            dp.put(rest, 0);
            return dp.get(rest);
        }

        int next = Integer.MAX_VALUE;
        // 搞定rest的第一张贴纸是啥
        for (String first : arr) {
            char[] firstChars = first.toCharArray();
            HashMap<Character, Integer> firstMap = new HashMap<>();
            for (int i = 0; i < firstChars.length; i++) {
                if (firstMap.containsKey(firstChars[i])) {
                    firstMap.put(firstChars[i], firstMap.get(firstChars[i]) + 1);
                } else {
                    firstMap.put(firstChars[i], 1);
                }
            }
            char[] oldRestChars = rest.toCharArray();
            HashMap<Character, Integer> oldRestMap = new HashMap<>();
            for (int i = 0; i < oldRestChars.length; i++) {
                if (oldRestMap.containsKey(oldRestChars[i])) {
                    oldRestMap.put(oldRestChars[i], oldRestMap.get(oldRestChars[i]) + 1);
                } else {
                    oldRestMap.put(oldRestChars[i], 1);
                }
            }
            // TODO（强调）：如果first中一个字符也不在rest中，直接跳过这张贴纸，
            //  containNumber用于记录rest中有几个first中的字符，
            //  下面如果发现containNumber依旧为0，直接跳过当前的贴纸
            int containNumber = 0;

            // old-first
            HashMap<Character, Integer> newRestMap = new HashMap<>();
            Set<Character> oldCharacters = oldRestMap.keySet();
            for (Character ch : oldCharacters) {
                if (firstMap.containsKey(ch) && (firstMap.get(ch) < oldRestMap.get(ch))) {
                    containNumber++;
                    newRestMap.put(ch, oldRestMap.get(ch) - firstMap.get(ch));
                } else if (firstMap.containsKey(ch) && (firstMap.get(ch) >= oldRestMap.get(ch))) {
                    containNumber++;
                    continue;
                } else {
                    newRestMap.put(ch, oldRestMap.get(ch));
                }
            }
            if (containNumber==0){
                continue;
            }
            String newRest = "";
            Set<Character> newRestCharacters = newRestMap.keySet();
            for (Character newCh : newRestCharacters) {
                int count = newRestMap.get(newCh);
                for (int i = 1; i <= count; i++) {
                    newRest += newCh;
                }
            }
            int cur = myCacheProcess(newRest, arr, dp);
            // 当前使用了1张贴纸所以cur+1
            next = Math.min(next, cur+1);
            dp.put(rest, next);
        }

        return dp.get(rest);
    }




























    public static int minStickers1(String[] stickers, String target) {

        int n = stickers.length;
        // stickers -> [26] [26] [26]
        int[][] map = new int[n][26];
        // 生成词频统计
        for (int i = 0; i < n; i++) {
            char[] str = stickers[i].toCharArray();
            for (char c : str) {
                // 第i号贴纸
                map[i][c - 'a']++;
            }
        }
        // 傻缓存 rest---->ans
        HashMap<String, Integer> dp = new HashMap<>();
        // base case
        dp.put("", 0);
        // dp：啥缓存
        // map剩余词频统计
        // target剩余目标
        return process1(dp, map, target);
    }

    // dp 傻缓存，如果rest已经算过了，直接返回dp中的值
    // rest 剩余的目标
    // 0..N每一个字符串所含字符的词频统计
    // 返回值是-1，map 中的贴纸  怎么都无法rest
    public static int process1(HashMap<String, Integer> dp, int[][] map, String rest) {
        if (dp.containsKey(rest)) {
            return dp.get(rest);
        }

        // 以下就是正式的递归调用过程
        int ans = Integer.MAX_VALUE; // ans -> 搞定rest，使用的最少的贴纸数量
        // N种贴纸
        int n = map.length;
        // tmap 去替代 rest
        int[] tmap = new int[26];
        char[] target = rest.toCharArray();
        for (char c : target) {
            tmap[c - 'a']++;
        }

        for (int i = 0; i < n; i++) {
            // 枚举当前第一张贴纸是谁？

            // 当前贴纸0位置的字符，i号贴纸有没有
            if (map[i][target[0] - 'a'] == 0) {
                continue;
            }

            StringBuilder sb = new StringBuilder();
            // i 号贴纸， j 枚举a~z字符
            for (int j = 0; j < 26; j++) { //
                if (tmap[j] > 0) { // j这个字符是target需要的
                    for (int k = 0; k < Math.max(0, tmap[j] - map[i][j]); k++) {
                        sb.append((char) ('a' + j));
                    }
                }
            }
            // sb ->  i
            String s = sb.toString();
            int tmp = process1(dp, map, s);
            if (tmp != -1) {
                ans = Math.min(ans, 1 + tmp);
            }
        }
        // ans 系统最大  rest
        dp.put(rest, ans == Integer.MAX_VALUE ? -1 : ans);
        return dp.get(rest);
    }

    public static int minStickers2(String[] stickers, String target) {
        int n = stickers.length;
        int[][] map = new int[n][26];
        for (int i = 0; i < n; i++) {
            char[] str = stickers[i].toCharArray();
            for (char c : str) {
                map[i][c - 'a']++;
            }
        }
        char[] str = target.toCharArray();
        int[] tmap = new int[26];
        for (char c : str) {
            tmap[c - 'a']++;
        }
        HashMap<String, Integer> dp = new HashMap<>();
        int ans = process2(map, 0, tmap, dp);
        return ans;
    }

    public static int process2(int[][] map, int i, int[] tmap, HashMap<String, Integer> dp) {
        StringBuilder keyBuilder = new StringBuilder();
        keyBuilder.append(i + "_");
        for (int asc = 0; asc < 26; asc++) {
            if (tmap[asc] != 0) {
                keyBuilder.append((char) (asc + 'a') + "_" + tmap[asc] + "_");
            }
        }
        String key = keyBuilder.toString();
        if (dp.containsKey(key)) {
            return dp.get(key);
        }
        boolean finish = true;
        for (int asc = 0; asc < 26; asc++) {
            if (tmap[asc] != 0) {
                finish = false;
                break;
            }
        }
        if (finish) {
            dp.put(key, 0);
            return 0;
        }
        if (i == map.length) {
            dp.put(key, -1);
            return -1;
        }
        int maxZhang = 0;
        for (int asc = 0; asc < 26; asc++) {
            if (map[i][asc] != 0 && tmap[asc] != 0) {
                maxZhang = Math.max(maxZhang, (tmap[asc] / map[i][asc]) + (tmap[asc] % map[i][asc] == 0 ? 0 : 1));
            }
        }
        int[] backup = Arrays.copyOf(tmap, tmap.length);
        int min = Integer.MAX_VALUE;
        int next = process2(map, i + 1, tmap, dp);
        tmap = Arrays.copyOf(backup, backup.length);
        if (next != -1) {
            min = next;
        }
        for (int zhang = 1; zhang <= maxZhang; zhang++) {
            for (int asc = 0; asc < 26; asc++) {
                tmap[asc] = Math.max(0, tmap[asc] - (map[i][asc] * zhang));
            }
            next = process2(map, i + 1, tmap, dp);
            tmap = Arrays.copyOf(backup, backup.length);
            if (next != -1) {
                min = Math.min(min, zhang + next);
            }
        }
        int ans = min == Integer.MAX_VALUE ? -1 : min;
        dp.put(key, ans);
        return ans;
    }

    public static void main(String[] args) {
        String[] arr = {"aaaa", "bbaa", "ccddd"};
        String str = "abcccccdddddbbbaaaaa";
        System.out.println(minStickers1(arr, str));
        System.out.println(minStickers2(arr, str));
        System.out.println("=========================");
        System.out.println(myMain(str, arr));
        System.out.println(myCacheMain(str, arr));

    }

}
